package com.wuyou.simple;

import java.util.Arrays;

/**
 * 1619. 删除某些元素后的数组均值
 */
public class TrimMean {

    public double solution_2(int[] arr){
        int[] max = new int[arr.length / 20];
        int[] min = new int[arr.length / 20];
        for (int i = 0; i < min.length; i++) {
            min[i] = Integer.MAX_VALUE;
        }
        int sum = 0;
        for (int i : arr) {
            sum += i;
            sortArr(max, min, i);
        }
        for (int i = 0; i < min.length; i++) {
            sum -= min[i];
            sum -= max[i];
        }
        return sum / (arr.length * 0.9);
    }

    private void sortArr(int[] max, int[] min, int x) {
        for (int i = 0; i < max.length; i++) {
            if (x < max[i]) break;
            if (i > 0) max[i - 1] = max[i];
            max[i] = x;
        }
        for (int i = 0; i < min.length; i++) {
            if (x > min[i]) break;
            if (i > 0) min[i - 1] = min[i];
            min[i] = x;
        }
    }

    public double solution_1(int[] arr){
        Arrays.sort(arr);
        double a = arr.length * 0.05;

        int sum = 0;
        for (int i = (int) a; i < arr.length - a; i++) {
            sum += arr[i];
        }
        return sum / (arr.length - (2 * a));
    }
}
